from typing import List, Set, Dict, Optional
from collections import defaultdict
import math

from chernc.treediff.gumtree.matchers.configuration_options import ConfigurationOptions
from chernc.treediff.gumtree.matchers.gumtree_properties import GumtreeProperties
from chernc.treediff.gumtree.matchers.mapping_store import MappingStore
from chernc.treediff.gumtree.matchers.matcher import Matcher
from chernc.treediff.gumtree.matchers.optimal.zs.zs_matcher import ZsMatcher
from chernc.treediff.gumtree.matchers.similarity_metrics import SimilarityMetrics
from chernc.treediff.gumtree.tree.tree import TreeLike
from chernc.treediff.gumtree.tree.tree_utils import TreeUtils
from chernc.treediff.gumtree.utils.sequence_algorithms import SequenceAlgorithms

class HybridBottomUpMatcher(Matcher):
    DEFAULT_SIZE_THRESHOLD = 20
    DEFAULT_SIM_THRESHOLD = float('nan')

    def __init__(self):
        self.size_threshold = self.DEFAULT_SIZE_THRESHOLD
        self.sim_threshold = self.DEFAULT_SIM_THRESHOLD

    def configure(self, properties: 'GumtreeProperties'):
        self.size_threshold: int = properties.try_configure(ConfigurationOptions.bu_minsize, self.size_threshold)
        self.sim_threshold: float = properties.try_configure(ConfigurationOptions.bu_minsim, self.sim_threshold)

    def match(self, src: 'TreeLike', dst: 'TreeLike', mappings: 'MappingStore') -> 'MappingStore':
        for t in src.post_order():
            if t.is_root():
                mappings.add_mapping(t, dst)
                self.last_chance_match(mappings, t, dst)
                break
            elif not (mappings.is_src_mapped(t) or t.is_leaf()):
                candidates = self.get_dst_candidates(mappings, t)
                best = None
                max_sim = -1.0
                t_size = len(t.get_descendants())

                for candidate in candidates:
                    threshold = 1 / (1 + math.log(len(candidate.get_descendants()) + t_size)) if math.isnan(self.sim_threshold) else self.sim_threshold
                    sim = SimilarityMetrics.chawathe_similarity(t, candidate, mappings)
                    if sim > max_sim and sim >= threshold:
                        max_sim = sim
                        best = candidate

                if best is not None:
                    self.last_chance_match(mappings, t, best)
                    mappings.add_mapping(t, best)
            elif mappings.is_src_mapped(t) and mappings.has_unmapped_src_children(t) and mappings.has_unmapped_dst_children(mappings.get_dst_for_src(t)):
                self.last_chance_match(mappings, t, mappings.get_dst_for_src(t))

        return mappings

    def get_dst_candidates(self, mappings: 'MappingStore', src: 'TreeLike') -> List['TreeLike']:
        seeds = []
        for c in src.get_descendants():
            m = mappings.get_dst_for_src(c)
            if m is not None:
                seeds.append(m)

        candidates = []
        visited = set()
        for seed in seeds:
            while seed.get_parent() is not None:
                parent = seed.get_parent()
                if parent in visited:
                    break
                visited.add(parent)
                if parent.get_type() == src.get_type() and not mappings.is_dst_mapped(parent) and not parent.is_root():
                    candidates.append(parent)
                seed = parent

        return candidates

    def last_chance_match(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        if src.get_metrics().size < self.size_threshold or dst.get_metrics().size < self.size_threshold:
            self.optimal_last_chance_match(mappings, src, dst)
        else:
            self.simple_last_chance_match(mappings, src, dst)

    def optimal_last_chance_match(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        m = ZsMatcher()
        zs_mappings = m.match(src, dst, MappingStore(src, dst))
        for candidate in zs_mappings:
            src_cand = candidate.src
            dst_cand = candidate.dst
            if mappings.is_mapping_allowed(src_cand, dst_cand):
                mappings.add_mapping(src_cand, dst_cand)

    def simple_last_chance_match(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        self.lcs_equal_matching(mappings, src, dst)
        self.lcs_structure_matching(mappings, src, dst)
        if src.is_root() and dst.is_root():
            self.histogram_matching(mappings, src, dst)
        elif not (src.is_root() or dst.is_root()):
            if src.get_parent().get_type() == dst.get_parent().get_type():
                self.histogram_matching(mappings, src, dst)

    def lcs_equal_matching(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        src_children = src.get_children()
        dst_children = dst.get_children()

        lcs = SequenceAlgorithms.longest_common_subsequence_with_isomorphism(src_children, dst_children)
        for x in lcs:
            t1 = src_children[x[0]]
            t2 = dst_children[x[1]]
            if mappings.are_srcs_unmapped(TreeUtils.pre_order(t1)) and mappings.are_dsts_unmapped(TreeUtils.pre_order(t2)):
                mappings.add_mapping_recursively(t1, t2)

    def lcs_structure_matching(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        src_children = src.get_children()
        dst_children = dst.get_children()

        lcs = SequenceAlgorithms.longest_common_subsequence_with_isostructure(src_children, dst_children)
        for x in lcs:
            t1 = src_children[x[0]]
            t2 = dst_children[x[1]]
            if mappings.are_srcs_unmapped(TreeUtils.pre_order(t1)) and mappings.are_dsts_unmapped(TreeUtils.pre_order(t2)):
                mappings.add_mapping_recursively(t1, t2)

    def histogram_matching(self, mappings: 'MappingStore', src: 'TreeLike', dst: 'TreeLike'):
        src_children = src.get_children()
        dst_children = dst.get_children()

        src_histogram: Dict[str, List['TreeLike']] = defaultdict(list)
        for c in src_children:
            src_histogram[c.get_type()].append(c)

        dst_histogram: Dict[str, List['TreeLike']] = defaultdict(list)
        for c in dst_children:
            dst_histogram[c.get_type()].append(c)

        for t in src_histogram.keys():
            if t in dst_histogram and len(src_histogram[t]) == 1 and len(dst_histogram[t]) == 1:
                t1 = src_histogram[t][0]
                t2 = dst_histogram[t][0]
                if mappings.are_both_unmapped(t1, t2):
                    mappings.add_mapping(t1, t2)
                    self.last_chance_match(mappings, t1, t2)

    def get_applicable_options(self) -> Set[ConfigurationOptions]:
        return {ConfigurationOptions.bu_minsize}